Doubling → Bifurcation search
When dichotomous search is performed on doubling results, it is simpler and faster to make the code tightly coupled than to think of them as separate parts. code:python
# find x s.t. f(x) = y
x = 0
for i in range(30 - 1, -1, -1):
if y >= dy:
y -= dy
x += 2 ** i
code:python
for i in range(30 - 1, -1, -1):
if countdown >= up:
countdown -= up
ret += 2 ** i
relevance
When I verified with AOJ, it was a TLE unless I used this bisecting search method.
---
This page is auto-translated from /nishio/ダブリング→二分探索. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.